/**

Given an array of integers, write some code to find all the 
integers that appear more than once in the array, 
sorted by which appears most often to least often (once)

X.Z. Liang
**/
#include<iostream>
#include<vector>
using namespace std;

inline void swap(int &a,int &b);

void quickSort(int *arr, int  left, int  right);


int main(){
    
    
    // the data to be processed
    const int AMOUNT = 15;
    int a[AMOUNT] = {1,1,1,3,3,2,1,2,3,2,7,7,7,3,2};
    
    //sorting the array with quicksort first
    quickSort(a,0,AMOUNT-1);    
    
    //insert  the number with same occurance times into the same buckets
    vector<int> *buckets = new vector<int>[AMOUNT];
    int temp = a[0];
    int count = 0;
    for(int i=0;i<=AMOUNT;i++){
            if(i == AMOUNT){
                 buckets[count].push_back(temp);
                 break;
            }
            if(temp == a[i]){
                    count++;   
            }else{
                  buckets[count].push_back(temp);
                  temp = a[i];
                  count = 1;
            }
    }
    
    //flush the result from buckets to new array 
    int top = AMOUNT-1;
    int index = 0;
    int *new_array = new int[AMOUNT];
    for(int i=top;i>=1;i--){
            while(!buckets[i].empty()){
                  int temp = buckets[i].back();
                  for(int j=0;j<i;j++){
                          new_array[index] = temp;
                          index++;
                  }
                  buckets[i].pop_back();
            }
    }
    delete []buckets;
    buckets = 0;
    
    //output the result
    for(int i=0;i<AMOUNT;i++){
          cout<<new_array[i]<<" ";
    }
    
    return 0;
}

//swap 2 int
inline void swap(int &a,int &b){
       int tmp = a;
       a = b;
       b = tmp;
}

//sort an array
void quickSort(int *arr,  int  left, int  right) {
      int i = left;
      int j = right;
      int tmp;
      int pivot = arr[(left + right) / 2]; 
      while (i <= j) {
            while (arr[i] < pivot){
                  i++;
            }
            while (arr[j] > pivot){
                  j--;
            }
            if (i <= j) {
                  swap(arr[j],arr[i]);
                  i++;
                  j--;
            }
      }
      if(left<j){
            quickSort(arr, left, j);
      }
      if(i<right){
            quickSort(arr, i, right);
      }
}
